package Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Tree
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-26  23:49
 * @Description: TODO
 * @Version: 1.0
 */
public class 二叉搜索树的验证98 {
    // 采用中序遍历来实现 空间需要o(N) 时间为O(N)
    //
    long maxvalue = Long.MIN_VALUE;
    // 采用双指针的方式来实现
    TreeNode pre;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        List<Integer> list = new ArrayList<>();
        dfs(root, list);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) < list.get(i - 1)) {
                return false;
            }
        }
        return true;
    }

    private void dfs(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            dfs(root.left, list);
        }
        list.add(root.val);
        if (root.right != null) {
            dfs(root.right, list);
        }
    }

    public boolean isValidBST2(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左
        boolean left = isValidBST(root.left);
        // 中
        if (root.val > maxvalue) {
            maxvalue = root.val;
        } else {
            return false;
        }
        // 右
        boolean right = isValidBST(root.right);
        return left && right;
    }

    public boolean isValidBST3(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左
        boolean left = isValidBST(root.left);
        // 中
        if (pre != null && pre.val >= root.val) {
            return false;
        }
        pre = root;
        // 右
        boolean right = isValidBST(root.right);
        return left && right;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
